package com.mashibing.class22;

/**
 * 给定一个正数n，求n的裂开方法数，
 * 规定：后面的数不能比前面的数小
 * 比如4的裂开方法有：
 * 1+1+1+1、1+1+2、1+3、2+2、4
 * 5种，所以返回5
 */
public class Code03_SplitNumber {
    // n为正数
    public static int ways(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return process(1, n);
    }

    // 上一个拆出来的数是pre
    // 还剩rest需要去拆
    // 返回拆解的方法数
    public static int process(int pre, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (pre > rest) {
            return 0;
        }
        int ways = 0;
        for (int first = pre; first <= rest; first++) {
            ways += process(first, rest - first);
        }
        return ways;
    }

    // 由pre(前置数) 和 rest(剩余数) 构成了一个二维数组.
    public static int dp1(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[][] dp = new int[n + 1][n + 1];
        // pre 是没有等于0的时候.
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for (int pre = n - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                int ways = 0;
                for (int first = pre; first <= rest; first++) {
                    ways += dp[first][rest - first];
                }
                // dp[pre][rest] = dp[pre][rest - pre] +
                //                 dp[pre+1][rest - pre - 1] +
                //                 dp[pre+2][rest - pre - 2] +
                //                 .... +
                //                 dp[rest][0]
                dp[pre][rest] = ways;
            }
        }
        return dp[1][n];
    }

    public static int dp2(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for (int pre = n - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                // dp[pre][rest] = dp[pre][rest - pre] +
                //                 dp[pre+1][rest - pre - 1] +
                //                 dp[pre+2][rest - pre - 2] +
                //                 .... +
                //                 dp[rest][0]
                //dp[pre + 1][rest] = { dp[pre+1][rest - pre - 1] + dp[pre+2][rest - pre - 2]
                //  +.... + dp[rest][0]}
                // 所以  dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre]
                // 譬如 : pre = 3 rest = 6 则 dp[3][6] = dp[3][3] + dp[4][2] + dp[5][1] + dp[6][0]
                //       pre = 4 rest = 6    dp[4][6] = dp[4][2] + dp[5][1] + dp[6][0]
                dp[pre][rest] = dp[pre + 1][rest];
                dp[pre][rest] += dp[pre][rest - pre];
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        int test = 39;
        System.out.println(ways(test));
        System.out.println(dp1(test));
        System.out.println(dp2(test));
    }
}
